package com.heima.leetcode.datastructure.array;

/**
 * <h2>合并两个有序数组 88</h2>
 */
public class MergeTwoSortedArray {

    /**
     * <h3>方法一，递归</h3>
     * 合并两个有序数组
     *
     * @param arr1 数组一
     * @param arr2 数组二
     * @return 合并后排好序的数组
     */
    public static int[] mergeTwoSortedArray1(int[] arr1, int[] arr2) {
        int[] arrSource = concatArray(arr1, arr2);
        int[] arr = new int[arrSource.length];
        mergeTwoSortedArray(arr, 0, arrSource, 0, arr1.length, arr1.length);
        return arr;
    }

    /**
     * <h3>方法二，指针</h3>
     * 合并两个有序数组
     * @param arr1 数组一
     * @param arr2 数组二
     * @return 合并后的数组
     */
    public static int[] mergeTwoSortedArray2(int[] arr1, int[] arr2) {
        int i = 0, j = 0;
        int[] arr = new int[arr1.length + arr2.length];
        for (int k = 0; k < arr.length; k++) {
            if (i >= arr1.length) {
                System.arraycopy(arr2, j, arr, k, arr2.length - j);
                break;
            }
            if (j >= arr2.length) {
                System.arraycopy(arr1, i, arr, k, arr1.length - i);
                break;
            }
            if (arr1[i] < arr2[j]) {
                arr[k] = arr1[i];
                i++;
            } else {
                arr[k] = arr2[j];
                j++;
            }
        }
        return arr;
    }

    /**
     * 用递归实现合并两个有序数组
     *
     * @param arr       合并后新的数组
     * @param start     新的数组的索引
     * @param arrSource 源数组
     * @param i         前半有序数组的索引i
     * @param lengthI   前半有序数组的长度
     * @param j         后半有序数组的索引j
     */
    private static void mergeTwoSortedArray(int[] arr, int start, int[] arrSource, int i, int lengthI, int j) {
        // 终止条件
        if (i >= lengthI) {
            // 前半已经遍历完了
            System.arraycopy(arrSource, j, arr, start, arrSource.length - j);
            return;
        }
        if (j >= arrSource.length) {
            // 后半已经遍历完了
            System.arraycopy(arrSource, i, arr, start, lengthI - i);
            return;
        }
        // 递的时候判断最小的数
        if (arrSource[i] < arrSource[j]) {
            arr[start] = arrSource[i];
            mergeTwoSortedArray(arr, start + 1, arrSource, i + 1, lengthI, j);
        } else {
            arr[start] = arrSource[j];
            mergeTwoSortedArray(arr, start + 1, arrSource, i, lengthI, j + 1);
        }
        // 归的时候啥也不做
    }

    /**
     * 直接拼接两个数组
     *
     * @param arr1 数组一
     * @param arr2 数组二
     * @return 拼接好的数组
     */
    private static int[] concatArray(int[] arr1, int[] arr2) {
        if (arr1 == null && arr2 == null) {
            return null;
        }
        if (arr1 == null) {
            return arr2;
        }
        if (arr2 == null) {
            return arr1;
        }
        int[] arr = new int[arr1.length + arr2.length];
        System.arraycopy(arr1, 0, arr, 0, arr1.length);
        System.arraycopy(arr2, 0, arr, arr1.length, arr2.length);
        return arr;
    }
}
